Typically, circular First In--First Out (FIFO) buffers or queues exist for numerous purposes including utilizing available memory resources effectively and repetitively, storing information where short term data transfer rates exceed the available temporary processing or transferring ability of the microprocessors or the like, and for temporary storage of data where the data size is limited but presently unknown or likely to be variable. FIFO buffers or queues can also be used for servicing hardware interrupts, cycling of software programs, for data shifting or manipulations, and for other purposes well known in the art. Circular FIFO buffers have likewise proven beneficial in the transfer of data both to and from communication devices and for other communication related applications. Typically, in certain communications applications or data transfer applications, the FIFO buffer or queue is first implemented in the hardware transmitting data or the hardware receiving data. Additional circular buffers or queues can be employed to move the received or transmitted data from or to the receiving or transmitting hardware.
Current FIFO buffers can be realized using one or more of many different mechanisms, including hardware implementation, software allocation, or a combination employing both hardware and software. A hardware implementation could include dedicated memory of a Central Processing Unit (CPU) using Dynamic Random Access Memories (DRAM), high speed memory, cache memory, or the like. Generally, at least two pointers are implemented in a circular FIFO buffer or queue. For example, the write pointer maintains the next or current available position in or for writing in the DRAM, memory, or storage space. The read pointer maintains the next or current position for retrieving data from the DRAM, memory, or storage space. It is customary to refer to the read pointer and write pointer as head pointer and tail pointer, or vice-versa, and therefore, herein they will be referred to specifically as `read pointer` and `write pointer` for clarity.
Additional types of control elements may be implemented in a circular queue or buffer. Optional pointers can exist for control in a circular FIFO buffer or system, including a data end pointer, one or more transfer pointers for execution of branching instructions, as well as others. Furthermore, one or more indexes or flags or the actual queue or buffer data can be used to implement queue or buffer control.
Optional control elements for the queue include buffer status indicators such as queue full, queue almost full, queue empty, queue almost empty, as well as other optional indicators such as data packet size, data size, transfer complete, data overrun, invalid request, free-count, used-count, a data loaded flag, and the like. These control elements have been added to circular queues to monitor or implement the `circular` behavior of the queue, while actually implementing the circular queue using a linear physical addressing scheme or in a linear or matrixed (x by y addressing) memory array or data storage structure.
Referring briefly to FIG. 2a, shown is a general overview of a prior art circular queue, or FIFO buffer, comprising numerous individual buffer storage elements 104, a physical start address 117 which may be referenced by a logical start address 116, a physical end address 121 which may be referenced by a logical end address 120, a write address pointer 108, and a read address pointer 112. The `circular` nature of this FIFO queue is shown by demonstrative return path 125, whereby upon reaching logical end address 120 or physical end address 121, the appropriate pointer resets to the logical start address 116 or physical start address 117. In effect and by deliberate implementation, as physical end address 121 is reached, the incrementation of any particular logical or physical pointer referencing storage elements within the circular queue 200, including either read address pointer 112 or write address pointer 108, results in the pointer crossing the physical end address 121 to be reset to the logical or physical address at the physical start address 117. For pointer addresses which exceed physical end address 121, then to determine the appropriate pointer address within the circular queue, a multiplicative factor of physical end address 121 minus physical start address 117 is subtracted from the pointer address to reduce its value to an address value less than the physical end address 121 but greater than or equal to the physical start address 117. In most present day systems, this is typically done by taking the modulus of the address divided by logical end address 120 when the logical start address 116 address is zero.
As demonstrated in FIG. 2a, the buffer storage elements 104 are entirely empty. The write address pointer 108 points to the first available data storage element which is unused and available for data storage. The read address pointer 112 likewise points to the last used buffer storage elements 104, or initialized (as shown therein) to the logical end address 120. As data is written into the circular queue 200, the buffer storage elements 104 fill as necessary to store data. As each portion or piece of data is written, a check is made to ensure write address pointer 108 has not exceeded logical end address 120 (or physical end address 121) and read address pointer 112. Thereafter, write address pointer 108 moves to point to the next available storage element address, as is shown in FIG. 2b by the storage of Data Groups (1) through (9), Upon reaching logical end address 120 or physical end address 121, the address of write address pointer 108 is reset to logical start address 116 or physical start address 117. As shown in FIG. 2b, no read process has yet occurred in the queue of FIG. 2b as the read address pointer 112 remains at its initialized position.
As shown in FIG. 2c, the operation of the circular queue 200 has completed data storage into each of the buffer storage elements 104, and has begun the reading process as data groups less than Data Group (24) have been read, as indicated by the shift in position of read address pointer 112. Also shown in FIG. 2c is the write of Data Group (31) across physical end address 121, resulting in a first data group portion being written (identified as Data Group (31A)) up to logical end address 120, and a second portion being written (identified as Data Group (31B)) starting from logical start address 116. Data Group (31A) in combination with Data Group (31B) is computationally or logically treated as a continuous single data group by the appropriate use of pointers, control functions, logic circuits and the like to effectively make a linear storage system of circular queue 200 appear or function `circular`.
Referring next to FIG. 2d, shown is circular queue 200 where the queue is functionally full of data comprised of the Data Groups (41)-(50). The storage element wherein write address pointer 108 and read address pointer 112 both reside in the same storage element wherein no presently valid data exists. Typically, write address pointer 108 is not permitted to proceed to (or in certain designs pass) the exact position of read address pointer 112. Likewise, read address pointer 112 is not permitted to proceed to (or in certain designs pass) the exact position of write address pointer 108. However, contingent upon the particular circular queue design, write address pointer 108 could proceed up to the exact position of read address pointer 112, or vice-versa. Such a design may require queue empty and/or queue full status bits, depending upon whether a read or whether a write procedure was occuring immediately prior to the equivalency of addresses for write address pointer 108 and read address pointer 112.